public class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,3,1};
        System.out.println(massage(arr));
        int[] arr1 = {2,3,2};
        System.out.println(rob(arr1));
    }
    //按摩师
    public static int massage(int[] nums) {
        int n = nums.length;
        //f表示到i位置时选i位置的值，此时时间最长
        int[] f = new int[n];
        //g表示到i位置时，不选i位置的值，此时时间最长
        int[] g = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            //到i位置必选
            f[i] = g[i-1] + nums[i];
            //到i位置不必选
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(g[n-1],f[n-1]);
    }
    public static   int rob(int[] nums) {
        int n = nums.length;
        if(n == 0 ) {
            return 0;
        }
        if(n == 1) {
            return nums[0];
        }
        //偷取第一个位置的值
        int a = nums[0] + rob1(nums,2,n-1);
        //不偷取第一个位置的值
        int b = rob1(nums,1,n);
        return Math.max(a,b);
    }
    private static int rob1(int[] nums,int start,int end) {
        if(start > end) {
            return 0;
        }
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[start] = nums[start];
        for (int i = start+1; i < end; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[end-1],g[end-1]);
    }
}
